package com.ctl.algorithm;

import org.apache.commons.lang3.StringUtils;

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.function.IntFunction;

/**
 * <p>Title: Test</p>
 * <p>Description: </p>
 * <p>Copyright: Copyright (c) 2019</p>
 * <p>Company: www.ctl.com</p>
 * 大顶堆、小顶堆及其建堆过程、堆排序
 * 大顶堆：每个结点的值都大于或等于其左右孩子结点的值；
 * 小顶堆：每个结点的值都小于或等于其左右孩子结点的值。
 * https://blog.csdn.net/u010002184/article/details/114146284
 *
 * @author ctl
 * @version 1.1
 * @date 2023-02-03 15:19
 */
public class BuildLargeOrSmallTopHeap {
    public static void main(String[] args) {
        int[] array = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        array = new int[]{32, 1, 33, 4, 5, 6, 7, 8, 10, 11, 12, 14, 15, 16, 18, 21, 22, 23, 24, 25, 27, 28, 31};
        Set<Integer> set = new HashSet<>();
        List<Integer> list =new ArrayList<>();
        for (int i = 0; i < 35; i++) {
            set.add(new Random().nextInt(35));
        }
        array = new int[set.size()];
        AtomicInteger j = new AtomicInteger();
        int[] finalArray = array;
        set.stream().forEach(iv -> finalArray[j.getAndIncrement()] = iv);
        array = new int[]{32, 1, 33, 4, 5, 6, 7, 8, 10, 11, 12, 14, 15, 16, 18, 21, 22, 23, 24, 25, 27, 28, 31, 67};
        array = new int[]{32, 1, 33, 4, 5, 6, 7, 8, 10, 11, 12, 14, 15, 16, 18, 21, 22, 23, 24, 25, 27, 28, 31};
        array = new int[]{32, 1, 33, 4, 5, 6, 7, 8, 10, 11, 12, 14, 15, 16, 18, 21, 22, 23, 24, 25, 27, 28, 31, 67, 34, 78};

        int max=85;
        int length=15+new Random().nextInt(max);
        set.clear();
        list.clear();
        for (int i = 0; i < length; i++) {
            set.add(new Random().nextInt(max));
        }
        array=new int[set.size()];
        list.addAll(set);
        for (int i = 0; i < list.size(); i++) {
            array[i]=list.get(i);
        }

        System.out.println("########################初始堆########################");
        printArray(array);
        heapPrint2(array);
        System.out.println("########################构建大顶堆########################");
        buildBigHeap(array, array.length);
        heapPrint2(array);
        System.out.println("########################大顶堆插入元素########################");
        array = addElementToLargeTopReactor(array,100);
        heapPrint2(array);
        System.out.println("########################大顶堆删除元素########################");
        array = removeElementFromLargeTopReactor(array);
        heapPrint2(array);
        System.out.println("########################大顶堆排序########################");
        sortLargeTopReactor(array, array.length);
        heapPrint2(array);
        printArray(array);

        array = new int[]{32, 1, 33, 4, 5, 6, 7, 8, 10, 11, 12, 14, 15, 16, 18, 21, 22, 23, 24, 25, 27, 28, 31, 67, 34, 78};
        System.out.println("########################初始堆########################");
        printArray(array);
        heapPrint2(array);
        System.out.println("########################构建小顶堆########################");
        buildSmallHeap(array, array.length);
        heapPrint2(array);
        System.out.println("########################小顶堆插入元素########################");
        array = addElementToSmallTopReactor(array,0);
        heapPrint2(array);
        System.out.println("########################小顶堆删除元素########################");
        array = removeElementFromSmallTopReactor(array);
        heapPrint2(array);
        System.out.println("########################小顶堆排序########################");
        sortSmallTopReactor(array, array.length);
        heapPrint2(array);
        printArray(array);


    }

    /**
     * 从大顶堆删除元素
     * @param array
     * @return
     */
    private static int[] removeElementFromLargeTopReactor(int[] array) {
        int[] arrayTmp = new int[array.length - 1];
        swap(array, 0, array.length - 1);
        System.arraycopy(array, 0, arrayTmp, 0, array.length - 1);
        array = arrayTmp;
        buildBigHeap(array, array.length);
        return array;
    }

    /**
     * 向大顶堆增加元素
     * @param array
     * @param element
     * @return
     */
    private static int[] addElementToLargeTopReactor(int[] array, int element) {
        int[] arrayTmp = new int[array.length + 1];
        System.arraycopy(array, 0, arrayTmp, 0, array.length);
        arrayTmp[arrayTmp.length - 1] = element;
        array = arrayTmp;
        buildBigHeap(array, array.length);
        return array;
    }

    /**
     * 从小顶堆删除元素
     * @param array
     * @return
     */
    private static int[] removeElementFromSmallTopReactor(int[] array) {
        int[] arrayTmp = new int[array.length - 1];
        swap(array, 0, array.length - 1);
        System.arraycopy(array, 0, arrayTmp, 0, array.length - 1);
        array = arrayTmp;
        buildSmallHeap(array, array.length);
        return array;
    }

    /**
     * 向小顶堆增加元素
     * @param array
     * @param element
     * @return
     */
    private static int[] addElementToSmallTopReactor(int[] array,int element) {
        int[] arrayTmp = new int[array.length + 1];
        System.arraycopy(array, 0, arrayTmp, 0, array.length);
        arrayTmp[arrayTmp.length - 1] = element;
        array = arrayTmp;
        buildSmallHeap(array, array.length);
        return array;
    }

    /**
     * 数组中元素的最大长度
     *
     * @param array
     * @return
     */
    static int getArrayEleMaxLength(int[] array) {
        int maxLength = 0;
        for (int i = 0; i < array.length; i++) {
            int length = String.valueOf(array[i]).length();
            if (maxLength < length) {
                maxLength = length;
            }
        }
        return maxLength;
    }

    /**
     * 获取数组对应的完全二叉树有几层
     *
     * @param arrayLength 数组长度
     * @return 0层1层次2层次(从0开始)
     */
    static int getLevel(int arrayLength) {
        return levelSum(0, 0, arrayLength);
    }

    private static int levelSum(int sum, int index, int length) {
        if (length == 1) {
            return 0;
        }
        sum += Math.pow(2, index);
        if (sum >= length) {
            return index;
        } else {
            return levelSum(sum, ++index, length);
        }
    }

    /**
     * level层的完美二叉树对应的数组长度(一个深度为k(>=-1)且有2^(k+1) - 1个结点的二叉树称为完美二叉树)
     * sum=index=0
     *
     * @param sum
     * @param level
     * @param index
     * @return
     */
    static int getPerfectBinaryTreeNodeNumByLevel(int sum, int level, int index) {
        if (level == 0) {
            return 1;
        }
        if (index > level) {
            return sum;
        } else {
            sum += Math.pow(2, index);
            return getPerfectBinaryTreeNodeNumByLevel(sum, level, ++index);
        }
    }

    /**
     * 打印数组 例如：int[] array=[1,2,3,4]打印结果为1,2,3,4
     *
     * @param array
     */

    private static void printArray(int[] array) {
        for (int i = 0; i < array.length; i++) {
            if (i == array.length - 1) {
                System.out.println(array[i]);
            } else {
                System.out.print(array[i] + ",");
            }
        }
    }

    /**
     * 构建大顶堆
     *
     * @param array
     * @param length
     */
    public static void buildBigHeap(int[] array, int length) {
        for (int i = length / 2 - 1; i >= 0; i--) {
            largeTopReactor(array, length, i);
        }
    }

    /**
     * 构建小顶堆
     *
     * @param array
     * @param length
     */
    public static void buildSmallHeap(int[] array, int length) {
        for (int i = length / 2 - 1; i >= 0; i--) {
            smallTopReactor(array, length, i);
        }
    }

    /**
     * 大顶堆
     *
     * @param array
     * @param length
     * @param index  节点在数组的索引(有叶子)
     */
    private static void largeTopReactor(int[] array, int length, int index) {
//        heapPrint2(array);
        //是否递归
        boolean deep = false;
        int maxArrayIndex = length - 1;
        int current = array[index];
        int left = array[2 * index + 1];
        if (2 * index + 2 < length) {//节点有左右
            int right = array[2 * index + 2];
            if (right > left && right > current) {
                swap(array, index, 2 * index + 2);
                maxArrayIndex = 2 * index + 2;
                deep = true;
            }
            if (left > right && left > current) {
                swap(array, index, 2 * index + 1);
                maxArrayIndex = 2 * index + 1;
                deep = true;
            }
        } else {//节点只有左边
            if (left > current) {
                swap(array, index, 2 * index + 1);
                maxArrayIndex = 2 * index + 1;
                deep = true;
            }
        }
        //该节点交换后判断是否有子节点,子节点该不该继续转换
        if (maxArrayIndex * 2 + 1 < length && deep) {
            largeTopReactor(array, length, maxArrayIndex);
        }
    }

    /**
     * 小顶堆
     *
     * @param array
     * @param length
     * @param index  节点在数组的索引(有叶子)
     */
    private static void smallTopReactor(int[] array, int length, int index) {
//        heapPrint2(array);
        //是否递归
        boolean deep = false;
        int smallArrayIndex = length - 1;
        int current = array[index];
        int left = array[2 * index + 1];
        if (2 * index + 2 < length) {//节点有左右
            int right = array[2 * index + 2];
            if (right < left && right < current) {
                swap(array, index, 2 * index + 2);
                smallArrayIndex = 2 * index + 2;
                deep = true;
            }
            if (left < right && left < current) {
                swap(array, index, 2 * index + 1);
                smallArrayIndex = 2 * index + 1;
                deep = true;
            }
        } else {//节点只有左边
            if (left < current) {
                swap(array, index, 2 * index + 1);
                smallArrayIndex = 2 * index + 1;
                deep = true;
            }
        }
        //该节点交换后判断是否有子节点,子节点该不该继续转换
        if (smallArrayIndex * 2 + 1 < length && deep) {
            smallTopReactor(array, length, smallArrayIndex);
        }
    }

    /**
     * 排序 大顶堆
     *
     * @param array
     * @param end
     */
    public static void sortLargeTopReactor(int array[], int end) {
        for (int i = end - 1; i >= 1; i--) {
            swap(array, 0, i);
//            buildBigHeap(array, i);
            if (i > 1) {
                largeTopReactor(array, i, 0);
            }
        }
    }

    /**
     * 排序 小顶堆
     *
     * @param array
     * @param end
     */
    public static void sortSmallTopReactor(int array[], int end) {
        for (int i = end - 1; i >= 1; i--) {
            swap(array, 0, i);
//            buildBigHeap(array, i);
            if (i > 1) {
                smallTopReactor(array, i, 0);
            }
        }
    }

    /**
     * 数组交换
     *
     * @param array
     * @param m
     * @param n
     */
    private static void swap(int array[], int m, int n) {
        int temp = array[m];
        array[m] = array[n];
        array[n] = temp;
    }


    public static void heapPrint(int[] array) {
        //数字的最大长度
        int arrayEleMaxLength = getArrayEleMaxLength(array);
        String blank = "";
        for (int a = 0; a < arrayEleMaxLength; a++) {
            blank += " ";
        }
        //数组长度
        int length = array.length;
        //树的深度0为第一层1为第二层
        int heapHeight = getLevel(array.length);
        int lastLevelLength = (int) Math.pow(2, heapHeight);
        for (int i = 0; i < length; i++) {
            //当前深度
            int level = getLevel(i + 1);
            //该深度长度
            int curLevelLength = (int) Math.pow(2, level);
            int curLevelFirstIndex = getPerfectBinaryTreeNodeNumByLevel(0, level, 0) - curLevelLength;
            int curLevelLastIndex = getPerfectBinaryTreeNodeNumByLevel(0, level, 0) - 1;
            if (i == curLevelFirstIndex) {
                //该层第一个元素
                int blankNum = (int) Math.pow(2, heapHeight - level) - 1;
                for (int j = 0; j < blankNum; j++) {
                    System.out.print(blank);
                }
                System.out.print(StringUtils.leftPad(String.valueOf(array[i]), arrayEleMaxLength, " "));
                //又是该层最后一个元素
                if (i == curLevelLastIndex) {
                    System.out.println();
                }
            } else if (i == curLevelLastIndex) {
                //该层最后一个元素
                midPad(arrayEleMaxLength, blank, heapHeight, lastLevelLength, level, curLevelLength, array[i]);
                System.out.println();
            } else {
                midPad(arrayEleMaxLength, blank, heapHeight, lastLevelLength, level, curLevelLength, array[i]);
            }
        }
    }

    private static void midPad(int arrayEleMaxLength, String blank, int heapHeight, int lastLevelLength, int level, int curLevelLength, int array) {
        int all = lastLevelLength * 2 - 1;
        int blankNum = (int) Math.pow(2, heapHeight - level) - 1;
        int a = (all - blankNum * 2 - curLevelLength) / (curLevelLength - 1);
        for (int j = 0; j < a; j++) {
            System.out.print(blank);
        }
        //该层中间元素
        System.out.print(StringUtils.leftPad(String.valueOf(array), arrayEleMaxLength, " "));
    }

    static int times = 0;

    public static void heapPrint2(int[] array) {
        System.out.println("times=" + (++times));
        StringBuffer buffer = new StringBuffer();
        //数字的最大长度
        int arrayEleMaxLength = getArrayEleMaxLength(array);
        String blank = "";
        for (int a = 0; a < arrayEleMaxLength; a++) {
            blank += " ";
        }
        //数组长度
        int length = array.length;
        //树的深度0为第一层1为第二层
        int heapHeight = getLevel(array.length);
        int lastLevelLength = (int) Math.pow(2, heapHeight);
        for (int i = 0; i < length; i++) {
            StringBuffer buf = new StringBuffer();
            //当前深度
            int level = getLevel(i + 1);
            //该深度长度
            int curLevelLength = (int) Math.pow(2, level);
            int curLevelFirstIndex = getPerfectBinaryTreeNodeNumByLevel(0, level, 0) - curLevelLength;
            int curLevelLastIndex = getPerfectBinaryTreeNodeNumByLevel(0, level, 0) - 1;
            if (i == curLevelFirstIndex) {
                //该层第一个元素
                int blankNum = (int) Math.pow(2, heapHeight - level) - 1;
                for (int j = 0; j < blankNum; j++) {
//                    System.out.print(blank);
                    buf.append(blank);
                }
//                System.out.print(StringUtils.leftPad(String.valueOf(array[i]), arrayEleMaxLength, " "));
                buf.append(StringUtils.leftPad(String.valueOf(array[i]), arrayEleMaxLength, "0"));
                //又是该层最后一个元素
                if (i == curLevelLastIndex) {
//                    System.out.println();
                    buf.append("\n");
                }
            } else if (i == curLevelLastIndex) {
                //该层最后一个元素
                midPad2(arrayEleMaxLength, blank, heapHeight, lastLevelLength, level, curLevelLength, array[i], buf);
//                System.out.println();
                buf.append("\n");

            } else {
                midPad2(arrayEleMaxLength, blank, heapHeight, lastLevelLength, level, curLevelLength, array[i], buf);
            }
            buffer.append(buf);
        }
        // System.out.println(buffer);
        String[] strings = buffer.toString().split("\n");
        for (int s = 0; s < strings.length; s++) {
            System.out.println(strings[s]);
            String str = strings[s].replaceAll("[\\d]+", StringUtils.leftPad("|", arrayEleMaxLength, " "));
            String str2 = str.replaceAll(" ", "");
            int length3 = str2.length();
            if (length3 % 2 == 0) {
                int[] indexArray = new int[length3];
                for (int i = 0; i < length3; i++) {
                    if (i == 0) {
                        indexArray[0] = str.indexOf("|", 0);
                    } else {
                        indexArray[i] = str.indexOf("|", indexArray[i - 1] + 1);
                    }
                }
                StringBuffer stringBuffer = new StringBuffer();
                stringBuffer.append(str);
                for (int i = 0; i < length3; i += 2) {
                    stringBuffer.replace(indexArray[i] + 1, indexArray[i + 1], StringUtils.leftPad("", indexArray[i + 1] - indexArray[i] - 1, "-"));
                }
                System.out.println(stringBuffer);
            } else {
                if (length3 > 0) {
                    int[] indexArray = new int[length3];
                    for (int i = 0; i < length3; i++) {
                        if (i == 0) {
                            indexArray[0] = str.indexOf("|", 0);
                        } else {
                            indexArray[i] = str.indexOf("|", indexArray[i - 1] + 1);
                        }
                    }
                    StringBuffer stringBuffer = new StringBuffer();
                    stringBuffer.append(str);
                    for (int i = 0; i < length3; i += 2) {

                        try {
                            stringBuffer.replace(indexArray[i] + 1, indexArray[i + 1], StringUtils.leftPad("", indexArray[i + 1] - indexArray[i] - 1, "-"));
                        } catch (Exception e) {
                        }
                    }
                    System.out.println(stringBuffer);
                }
            }
        }
    }

    private static void midPad2(int arrayEleMaxLength, String blank, int heapHeight, int lastLevelLength, int level, int curLevelLength, int array, StringBuffer buffer) {
        int all = lastLevelLength * 2 - 1;
        int blankNum = (int) Math.pow(2, heapHeight - level) - 1;
        int a = (all - blankNum * 2 - curLevelLength) / (curLevelLength - 1);
        for (int j = 0; j < a; j++) {
//            System.out.print(blank);
            buffer.append(blank);
        }
        //该层中间元素
//        System.out.print(StringUtils.leftPad(String.valueOf(array), arrayEleMaxLength, " "));
        buffer.append(StringUtils.leftPad(String.valueOf(array), arrayEleMaxLength, "0"));
    }
}
